home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / Book Chapters / 07 - Mechanics - Environment / Maze / Maze.c < prev    next >
C/C++ Source or Header  |  1995-03-12  |  5KB  |  206 lines
  1. /*
  2. Maze demo
  3.  
  4. by Ingemar Ragnemalm 1995
  5.  
  6. Demonstrates how to make a (constrained) distance transform for
  7. finding the shortest path through a maze.
  8. */
  9.  
  10.  
  11. /*Size of the array*/
  12. #define    kArraySizeH 15
  13. #define    kArraySizeV 12
  14.     
  15. /*Size of the tiles*/
  16. #define    kTileSizeH 24
  17. #define    kTileSizeV 24
  18.  
  19.  
  20. /* What does each tile contain? The destination is zero
  21. (more than one is permitted!), and the outermost enties
  22. must always be walls (-1). Edit this to try other layouts! */
  23.  
  24. short tileArray[kArraySizeH][kArraySizeV] = {
  25.     {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  26.     {-1,999,999,999, -1, -1, -1, -1, -1, -1,999, -1},
  27.     {-1,999,  0,999, -1, -1, -1, -1, -1, -1,999, -1},
  28.     {-1,999,999,999,999,999,999,999,999,999,999, -1},
  29.     {-1,999, -1,999, -1, -1,999,999,999, -1, -1, -1},
  30.     {-1, -1, -1,999, -1, -1,999, -1, -1, -1, -1, -1},
  31.     {-1, -1, -1,999, -1, -1,999, -1, -1, -1, -1, -1},
  32.     {-1, -1,999,999,999,999,999,999,999,999,999, -1},
  33.     {-1, -1,999,999, -1, -1, -1, -1, -1, -1,999, -1},
  34.     {-1, -1,999,999, -1, -1, -1, -1, -1, -1,999, -1},
  35.     {-1, -1, -1,999,999,999,999,999, -1, -1,999, -1},
  36.     {-1, -1, -1,999,999,999,999,999, -1, -1,999, -1},
  37.     {-1, -1, -1, -1, -1,999,999,999,999,999,999, -1},
  38.     {-1, -1, -1, -1, -1,999,999,999, -1, -1, -1, -1},
  39.     {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
  40.     };
  41.  
  42. /*All 8 directions as vectors*/
  43. Point directionTable[8] =
  44. {
  45.     {-1, 1 },
  46.     {-1, 0 },
  47.     {-1,-1 },
  48.     { 0,-1 },
  49.     { 1,-1 },
  50.     { 1, 0 },
  51.     { 1, 1 },
  52.     { 0, 1 }
  53. };
  54.  
  55. /* Pictures*/
  56. PicHandle wallTile;
  57.  
  58. /* A boolean for signalling if a change is made */
  59. Boolean    changeFlag;
  60.  
  61. /* Draw a tile */
  62.  
  63. static void DrawTile(short h, short v)
  64. {
  65.     Rect    tileRectangle;
  66.     Str255    tempString;
  67.  
  68.     SetRect(&tileRectangle, h * kTileSizeH, v * kTileSizeV, (h + 1) * kTileSizeH, (v + 1) * kTileSizeV);
  69.     if (tileArray[h][v] < 0)
  70.         DrawPicture(wallTile, &tileRectangle);
  71.     else
  72.     {
  73.         EraseRect(&tileRectangle);
  74.         MoveTo(h * kTileSizeH + 5, v * kTileSizeV + 18);
  75.         NumToString(tileArray[h][v], tempString);
  76.         DrawString(tempString);
  77.     }
  78. } /*DrawTile*/
  79.  
  80.  
  81. void DrawAllTiles()
  82. {
  83.     short h, v;
  84.  
  85.     for ( h = 0 ; h < kArraySizeH ; h++)
  86.         for ( v = 0 ; v < kArraySizeV ; v++)
  87.             DrawTile(h, v);    
  88. }
  89.  
  90.  
  91. /* Standard inits */
  92.  
  93. static void InitToolbox(void) {
  94.     InitGraf (&qd.thePort);
  95.     InitFonts ();
  96.     FlushEvents (everyEvent,0);
  97.     InitWindows ();
  98.     InitMenus ();
  99.     TEInit ();
  100.     InitDialogs (nil);
  101.     InitCursor ();
  102. } /*InitToolbox*/
  103.  
  104.  
  105.  
  106.  
  107. void DistanceTransformForward()
  108. {
  109.     short    h, v;
  110.     short    direction;
  111.     Point    neighbor;
  112.  
  113.     for ( v = 0 ; v < kArraySizeV ; v++)
  114.         for ( h = 0 ; h < kArraySizeH ; h++)
  115.         {
  116.             if (tileArray[h][v] > 0)
  117.             {
  118.                 for (direction = 0; direction < 4; direction++)
  119.                 {
  120.                     neighbor.h = h + directionTable[direction].h;
  121.                     neighbor.v = v + directionTable[direction].v;
  122.                     if (tileArray[neighbor.h][neighbor.v] >= 0)
  123.                         if (tileArray[neighbor.h][neighbor.v]+1 < tileArray[h][v])
  124.                         {
  125.                             tileArray[h][v] = tileArray[neighbor.h][neighbor.v]+1;
  126.                             changeFlag = true;
  127.                         }
  128.                 } // for directions 0..3
  129.             } // if >0
  130.         } // for all spaces
  131. } /*DistanceTransformForward*/
  132.  
  133.  
  134. void DistanceTransformBackward()
  135. {
  136.     short    h, v;
  137.     short    direction;
  138.     Point    neighbor;
  139.  
  140.     for ( v = kArraySizeV ; v >= 0 ; v--)
  141.         for ( h = kArraySizeH-1 ; h >= 0 ; h--)
  142.         {
  143.             if (tileArray[h][v] > 0)
  144.             {
  145.                 for (direction = 4; direction < 8; direction++)
  146.                 {
  147.                     neighbor.h = h + directionTable[direction].h;
  148.                     neighbor.v = v + directionTable[direction].v;
  149.                     if (tileArray[neighbor.h][neighbor.v] >= 0)
  150.                         if (tileArray[neighbor.h][neighbor.v]+1 < tileArray[h][v])
  151.                         {
  152.                             tileArray[h][v] = tileArray[neighbor.h][neighbor.v]+1;
  153.                             changeFlag = true;
  154.                         }
  155.                 } // for directions 0..3
  156.             } // if >0
  157.         } // for all spaces
  158. } /*DistanceTransformBackward*/
  159.  
  160.  
  161.  
  162. /****************** Main program ******************/
  163.  
  164. void main(void) {
  165.     WindowPtr    myWindow;
  166.     Rect    windowRectangle;
  167.     short    h,v;
  168.  
  169.     InitToolbox();
  170.  
  171. /*Set up the window*/
  172.     SetRect(&windowRectangle, 50, 50, 50 + kArraySizeH * kTileSizeH, 50 + kArraySizeV * kTileSizeV);
  173.     myWindow = NewCWindow(0L, &windowRectangle, "\pMaze demo", true, 0, (WindowPtr)-1L, false, 0);
  174.     SetPort(myWindow);
  175.     TextSize(9);
  176.  
  177. /* Load the picture*/
  178.     wallTile = GetPicture(128);            /*PICT resource #128.*/
  179.  
  180. /* Redraw */
  181.     DrawAllTiles();
  182.  
  183. /* Repeat the distance transform until no more changes occur! */
  184.     do
  185.     {
  186.         changeFlag = false;
  187.  
  188. /* Forward scan */
  189.         DistanceTransformForward();
  190.  
  191.         DrawAllTiles();
  192.  
  193. /* Backward scan */
  194.         DistanceTransformBackward();
  195.  
  196.         DrawAllTiles();
  197.     }
  198.     while (changeFlag);
  199.  
  200. /* Signal completion */
  201.     SysBeep(1);
  202.  
  203.     while ( ! Button () )
  204.         ;
  205. } /*Maze*/
  206.